﻿//编写一个函数来查找字符串数组中的最长公共前缀。
//如果不存在公共前缀，返回空字符串 ""。
//
//输入：strs = ["flower", "flow", "flight"]
//输出："fl"
//
//输入：strs = ["dog", "racecar", "car"]
//输出：""
//解释：输入不存在公共前缀。
//
//提示：
//	1 <= strs.length <= 200
//	0 <= strs[i].length <= 200
//	strs[i] 如果非空，则仅由小写英文字母组成

// class Solution {
// public:
//     string longestCommonPrefix(vector<string>& strs) {
//         // 解法一：两两比较

//         string ret = strs[0];
//         for (int i = 1; i < strs.size(); i++)
//             ret = findCommon(ret, strs[i]);
//         return ret;
//     }
//     string findCommon(string& s1, string& s2) {
//         int i = 0;
//         while (i < min(s1.size(), s2.size()) && s1[i] == s2[i])
//             i++;
//         return s1.substr(0, i);
//     }
// };

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        // 解法二：统一比较
        for (int i = 0; i < strs[0].size(); i++) {
            char tmp = strs[0][i];
            for (int j = 1; j < strs.size(); j++)
                if (i == strs[j].size() || tmp != strs[j][i])
                    return strs[0].substr(0, i);
        }
        return strs[0];
    }
};